The present invention relates to a public-key cryptosystem encryption method and ciphertext generating device for transforming a plaintext into a ciphertext by using a public key, a cryptographic communication method and cryptographic communication system using this encryption method, and a memory product/data signal embodied in carrier wave for recording/transmitting operation programs for these methods.
In the modern society, called a highly information-oriented society, based on a computer network, important business documents and image information are transmitted and communicated in a form of electronic information. Such electronic information can be easily copied, so that it tends to be difficult to discriminate its copy and original from each other, thus bringing about an important issue of data integrity. In particular, it is indispensable for establishment of a highly information oriented society to implement such a computer network that meets the factors of “sharing of computer resources,” “multi-accessing,” and “globalization,” which however includes various factors contradicting the problem of data integrity among the parties concerned. In an attempt to eliminate those contradictions, encrypting technologies which have been mainly used in the past military and diplomatic fields in the human history are attracting world attention as an effective method for that purpose.
A cipher is defined as exchanging information in such a manner that no one other than the parties concerned can understand the meaning of the information. In the field of ciphers, encryption is defined as converting an original text (plaintext) that can be understood by anyone into a text (ciphertext) that cannot be understood by the third party and decryption is defined as restoring a ciphertext into a plaintext, and cryptosystem is defined as the overall processes covering both encryption and decryption. The encrypting and decrypting processes use secret information called an encryption key and a decryption key, respectively. Since the secret decryption key is necessary in decryption, only those knowing this decryption key can decrypt ciphertexts, thus maintaining data security.
The encryption scheme is roughly classified into two types: common-key cryptosystem and public-key cryptosystem. In a common-key cryptosystem, an encryption key and a decryption key are identical with each other, and a sender and a recipient perform cryptographic communications by possessing an identical common key. The sender encrypts a plaintext based on a secret common key and transmits the resultant ciphertext to the recipient, and then the recipient decrypts the ciphertext into the original plaintext by using this common key.
On the other hand, in a public-key cryptosystem, an encryption key and a decryption key are different from each other, and cryptographic communications are performed by encrypting a plaintext by the sender with the use of a publicized public key of the recipient and decrypting the resultant ciphertext by the recipient with the use of its own secret key. The public key is a key used for encryption and the secret key is a key used for decrypting the ciphertext transformed by the public key, and the ciphertext transformed by the public key can be decrypted only by the secret key.
As one scheme of public-key cryptosystem, a product-sum type encryption scheme has been known. In this encryption scheme, the sender as one of entities generates ciphertext C=m1c1=m2c2= . . . +mKcK by using plaintext vector m=(m1, m2, . . . , mK) obtained by dividing plaintext into K pieces and base vector c=(c1, c2, . . . , cK) as a public key, and the recipient as the other entity decrypts the ciphertext C into the plaintext vector m by using a secret key to obtain the original plaintext.
Regarding the product-sum type cryptosystem using an operation on an integer ring, new schemes and attacking methods have been proposed one after another. In particular, development of encryption/decryption techniques capable of performing high-speed decryption has been desired so as to process a large quantity of information in a short time. Then, the present inventors proposed an encryption method and decryption method of the product-sum type cryptosystem, which enable high-speed decryption processing by expressing plaintext by using multi-adic numbers (Japanese Patent Application Laid-Open Nos. 2000-89668 and 2000-89669).
The following description will explain the encryption method and decryption method proposed in Japanese Patent Application Laid-Open No. 2000-89668 (hereinafter referred to as the “first conventional example”). The secret and public keys are prepared as follows.                Secret key: {bi}, {vi}, P, w        Public key: {ci}        
By multiplying a base-product b1b2 . . . bi by a random number term vi, a base Bi is given as shown by (1) below.Bi=vib1b2 . . . bi  (1)
Here, vi is set so that each Bi expressed by equation (1) has an almost equal size. However, the condition gcd(vi, bi=1)=1 must be satisfied.
With the use of a random number w, the public key {ci} is found as shown by (2) below.ci≡wBi(mod P)  (2)
By performing the product-sum operation of messages {mi} obtained by dividing the plaintext into K pieces and the public keys {ci}, the ciphertext C is obtained as shown by (3) below.C=m1c1+m2c2+ . . . +mKcK  (3)
Decryption processing is carried out as follows.
For the ciphertext C, an intermediate decrypted text M is found as shown by (4) below.M≡w−1C(mod P)  (4)
This intermediate decrypted text M is specifically given as equation (5), and it can be decrypted by a sequential decryption algorithm shown below.M=m1b1v1+m2b1b2v2+ . . . +mKb1b2 . . . bKvK  (5)[Sequential Decryption Algorithm]
Step 1M1=M/b1 m1=M1v1−1(mod b2)
Step i (i=2 to K−1)M1=(Mi−1−mi−1vi−1)/b1 m1≡Mivi−1(mod bi+1)
Step KMK=(MK−1−mK−1vK−1)/bK mK=MK/vK 
Originally, such a public-key encryption scheme bases its security on the difficulty of factoring and the difficulty of solving a discrete logarithm problem, and various attacks against it have been proposed.
Moreover, the present inventors proposed a new type of public-key cryptosystem encryption method which bases its security on such a point that a set of public keys can be freely selected among a very large number of combinations of public keys (Japanese Patent Application No. 11-269407/1999, hereinafter referred to as the “second conventional example”). This scheme is a modified scheme of the above-mentioned first conventional example. In this scheme, a plurality of public keys produced from the products of integers and random number terms are prepared in advance for each divided plaintext obtained by dividing a plaintext, an arbitrary public key is selected for each divided plaintext among these prepared public keys, and a ciphertext is generated by using the selected public keys. The following description will explain the encryption method and decryption method proposed in this second conventional example.
The intermediate decryped text M during the first transfer by the encryption scheme of the second conventional example based on the scheme of the first conventional example is given by (6) below.M=m1′b1v1+m2′b1b2v2+ . . . +mK′b1b2 . . . bKvK  (6)
However, m1′ is encoded to establish (7) below module J for j given by adding jog2 J-bit redundancy to message (divided plaintext) m1, and the information indicating which public key among later-described plurality of public keys is to be selected for each divided plaintext is transmitted.mi′≡j(mod J)  (7)
FIG. 1 is an illustration showing a public key list indicating a plurality of public keys prepared for each divided plaintext. In FIG. 1, K represents a dividing number (class number) of plaintext. As illustrated in FIG. 1, the set {b1b2 . . . bivi(j)} provided by multiplying the base-product by a random number term is prepared as J pieces of public keys for each divided plaintext (each class).
An entity as the recipient transforms these products of the base-product and random number term by a random number w and publicizes them. In other words, the products of the base-product and random number term shown in FIG. 1 are transformed as shown by (8) below, and the set {cij} thereof is publicized.b1b1 . . . bivi(j)w≡cij(mod P)  (8)
A set of public keys which is randomly selected by an entity as the sender is expressed as shown by (9) below. In this case, it is possible for the entity as the sender to select public keys in JK(>> 1) ways.
[Eq. 1](c1, j1, c2, j2, . . . , cK, jK)  (9)
According to a set of the selected public keys shown in (9) above, the entity as the sender lets mi′≡ji (mod J), and then generates the ciphertext C to the entity as the recipient as shown by (10) below.
[Eq. 2]C=m1′c1, j1+m2′c2, j2+ . . . +mK′cK, jK  (10)
In order to decrypt the ciphertext C thus generated, the entity as the recipient predetermines the random number term vi(j) of FIG. 1 as shown by (11) below.vi(j)=wb, i+ri(j)bi+l  (11)where each of wb, i, ri(j) is a random number.
Further, the entity as the recipient has wb, i−1 that satisfies (12) below as a secret key.wb, i·wb, i−1≡1(mod bi+l)  (12)
The decryption processing by the entity as the recipient is carried out as follows. An intermediate decrypted text M0 is given as shown by (13) below.
[Eq. 3]M0=m1′b1v1(j1)+m2′b1b2v2(j2)+ . . . +mK′b1b2, . . . bKvK(jK)  (13)
Therefore, decryption can be performed by the sequential decryption algorithm shown in (14) below. Incidentally, in (14), although bK+1 is a random number satisfying mK′<bK+i, it is not used as a base. In general, the random number term for ji in step i is expressed as shown by (15) below.                               [                      Eq            .                                                  ⁢            4                    ]                ⁢                                  ⁢        Sequential        ⁢                                  ⁢        Decryption        ⁢                                  ⁢        Algorithm                                                                                                                Step                ⁢                                                                  ⁢                1                                                                                                                                                                            M                        1                                            =                                            ⁢                                                                        M                          0                                                                          b                          1                                                                                                                                                                                                        m                        1                        ′                                            ≡                                            ⁢                                                                                                    M                            1                                                    ·                                                      w                                                          b                              ,                              i                                                                                      -                              1                                                                                                      ⁢                                                                                                  ⁢                                                  (                                                      mod                            ⁢                                                                                                                  ⁢                                                          b                              2                                                                                )                                                                                                                                                                                                        m                        1                        ′                                            ≡                                            ⁢                                                                        j                          i                                                ⁢                                                                                                  ⁢                                                  (                                                      mod                            ⁢                                                                                                                  ⁢                            J                                                    )                                                                                                                                                                                            Step                ⁢                                                                  ⁢                i                ⁢                                                                  ⁢                                  (                                      i                    =                                                                  2                        ⁢                                                                                                  ⁢                        to                        ⁢                                                                                                  ⁢                        K                                            -                      1                                                        )                                                                                                                                                                                            M                        i                                            =                                            ⁢                                                                                                    M                                                          i                              -                              1                                                                                -                                                                                    m                                                              i                                -                                                                  i                                  ′                                                                                                                      ⁢                                                          v                                                              i                                -                                1                                                                                            (                                                                  i                                                                      i                                    -                                    i                                                                                                  )                                                                                                                                                              b                          i                                                                                                                                                                                                        m                        i                        ′                                            ≡                                            ⁢                                                                        M                          i                                                ⁢                                                  w                                                      b                            ,                            i                                                                                -                            1                                                                          ⁢                                                                                                  ⁢                                                  (                                                      mod                            ⁢                                                                                                                  ⁢                                                          b                                                              i                                +                                1                                                                                                              )                                                                                                                                                                                                        m                        i                        ′                                            ≡                                            ⁢                                                                        j                          i                                                ⁢                                                                                                  ⁢                                                  (                                                      mod                            ⁢                                                                                                                  ⁢                            J                                                    )                                                                                                                                                                                            Step                ⁢                                                                  ⁢                K                                                                                                                                                                            M                        K                                            =                                            ⁢                                                                                                    M                                                          K                              -                              1                                                                                -                                                                                    m                                                              K                                -                                                                  1                                  ′                                                                                                                      ⁢                                                          v                                                              K                                -                                1                                                                                            (                                                                  j                                                                      K                                    -                                    1                                                                                                  )                                                                                                                                                              b                          K                                                                                                                                                                                                        m                        K                        ′                                            ≡                                            ⁢                                                                        M                          i                                                ⁢                                                  w                                                      b                            ,                            K                                                                                -                            1                                                                          ⁢                                                                                                  ⁢                                                  (                                                      mod                            ⁢                                                                                                                  ⁢                                                          b                                                              K                                +                                1                                                                                                              )                                                                                                                                                        }                            (        14        )                                v                  (                      j            i                    )                                    (        15        )            
In the decryption method proposed in the above-described second conventional example, since public keys are arbitrarily selected, i.e., since the entity as the sender freely selects public keys and generates ciphertext, the selection pattern of the public keys is unknown to attackers, and thus making it difficult to attack. Besides, the present inventors are further researching on a more practical encryption method.